1. Field of the Invention
The present invention relates to solving a constrained optimization problem.
2. Description of the Related Art
Recently, there has been a demand for solving constrained optimization problems in various industrial fields. A constrained optimization problem is defined as a problem to be solved by finding a point at which the value of an objective function is maximized or minimized within a subset of points subject to constraints. In other words, solving a constrained optimization problem is to formulate the problem and select the optimal solution from among possible solutions.
A constrained optimization problem may be applied to automated design, such as determining design parameters for obtaining a desired specification. More specifically, a constrained optimization problem may applied to finding a molecular structure having a minimum level of energy, determining the interface shape of two types of liquids, or a liquid and a gas, held in a container at a constant volume, or determining optimal lens shape, lens spacing, and lens material for obtaining a desired optical characteristic.
A typical constrained optimization problem of minimizing the value of a real function E(r)=0 subject to the constraint S(r)=0 will be described below. Here, r is an n-dimensional real vector
  r  =      (                                        r            1                                                            r            2                                                ⋮                                                  r            n                                )  The problem of maximizing the real function can be solved by inverting the positive and negative signs of the same objective function.
In general, an algorithm for solving an unconstrained optimization problem finds a point r at which a function E(r) is minimized, starting from an initial vector r(0), according to data related to a gradient vector T=−∇E(r).
However, the solutions of a constrained optimization problem cannot be obtained by such a simple algorithm. Therefore, various methods for solving a constrained optimization problem have been developed. Some typical methods include the penalty method and the multiplier method (the method of Lagrangian undetermined multipliers). These methods are described in Chapter 9 of “Shinban suchikeisan hando-bukku (New Edition of Numerical Calculation Handbook)” (Tokyo: Ohmsha, 1990) edited by Yutaka Ohno and Kazuo Isoda.
The penalty method adds a penalty function P(r) to the objective function E(r) so that the value of the function becomes 0 when the constraint holds and becomes significantly large when the constraint is violated. In other words, in the penalty method, a newly introduced objective function Ω(r)=E(r)+P(x) is minimized. A typical penalty function may be P(r)=ωS(r)2, where ω is a positive number that is adjusted to a suitable value in the process of finding the local minimum.
The multiplier method makes a newly introduced objective function Ω(r, λ)=E(r)+λS(r) stationary by introducing an undetermined multiplier λ. The objective function Ω(r, λ)=E(r)+λS(r) is subject to the constraint
            ∂              Ω        ⁡                  (                      r            ,            λ                    )                            ∂      λ        =  0which is a stationary condition of Ω(r) with respect to λ.
However, these known methods for solving a constrained optimization have the following problems. For the penalty method, selecting the penalty function becomes a problem. In the case of P(r)=ωS(r)2, unless the value of ω is adjusted satisfactorily, the results of the computation do not converge to the correct value.
For the method of Lagrangian undetermined multipliers, although a local minimum of E(r) is to be found, in actuality, in general, a saddle point of Ω(r) is obtained instead of the local minimum of Ω(r). Various algorithms for finding a saddle point have been proposed, but they are not as easy as the algorithms for finding local minima.